package com.shr.codem;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Four {
	private static List<Integer> maxPath = new ArrayList<>();
	private static int[] cost; 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int count = sc.nextInt();
			int[][] connectMatrix = new int[count+1][count+1]; 
			int[] headCount = new int[count+1];
			for(int i = 1;i<count;i++){
				int pre = sc.nextInt();
				int end = sc.nextInt();
				headCount[end] += 1;
				connectMatrix[pre][end] = 1;
				
			}
			cost = new int[count+1];
			for(int i = 1;i<cost.length;i++){
				cost[i] = sc.nextInt();
			}
			
			List<Integer> path = new ArrayList<>();
			path.add(1);
			int maxSize = 0;
			if(cost[1] > 1) {
				track(path, connectMatrix);
				maxSize = maxPath.size();
			}
			System.out.println(maxSize);
		}
		sc.close();
	}

	private static void track(List<Integer> path,int[][] matrixDist) {
		int last = path.get(path.size()-1) ;
		boolean flag = true;
		for(int i = 0;i<matrixDist[last].length;i++){
			if(matrixDist[last][i] == 1){
				flag = false;
				path.add(i);
				track(path,matrixDist);
			}
		}
		
		if(flag == true){
			if(maxPath.size() < path.size() && isQualified(path)){
				maxPath.clear();
				maxPath.addAll(path);
			}
		}
		path.remove(path.size()-1) ;
	}

	private static boolean isQualified(List<Integer> path) {
		int minVal = getMin(path);
		int maxDiv = 1;
		for(int i = 2;i <= minVal;i++){
			boolean flag = true;
			for(int k : path){
				if(cost[k] % i != 0){
					flag = false ;
					break ;
				}
			}
			if(flag)
				maxDiv = i;
		}
		if(maxDiv > 1)
			return true ;
		else return false ;
	}

	private static int getMin(List<Integer> path) {
		int minVal = cost[path.get(0)];
		for(int i = 1;i<path.size();i++){
			if(cost[path.get(i)]<minVal)
				minVal = cost[path.get(i)];
		}
		return minVal;
			
	}
}
